package leetcode;

import java.util.Objects;

/**
 * @author Liangyaoyun
 */
public class DoublePointerLinkedList {
    private static Node head;
    private static int size;
    public static class Node{
        public Node pre;
        public Node next;
        public String data;
        public Node(){
        }
        public Node(String data){
            this.data=data;
        }

        public void add(String s) {
            //1.创建一个新节点
            Node node=new Node(data);
            //2.判空，如果当前链表是空链表，则新添加的节点是头节点
            if (head==null){
                head=node;
                size++;
                return;
            }
            //3.找到最后一个节点
            Node n=head;
            while (n.next!=null){
                n=n.next;
            }
            //循环结束后，将新节点插到尾节点
            //新节点的前指针指向上一个节点
            node.pre=n;
            //倒数第二个节点的后指针指向新节点
            n.next=node;
            //新节点的后指针指向null
            node.next=null;
            //链表长度++
            size++;
        }
    }
    //相链表末尾添加一个节点
    public void add(String data){
        //1.创建一个新节点
        Node node=new Node(data);
        //2.判空，如果当前链表是空链表，则新添加的节点是头节点
        if (head==null){
            head=node;
            size++;
            return;
        }
        //3.找到最后一个节点
        Node n=head;
        while (n.next!=null){
            n=n.next;
        }
        //循环结束后，将新节点插到尾节点
        //新节点的前指针指向上一个节点
        node.pre=n;
        //倒数第二个节点的后指针指向新节点
        n.next=node;
        //新节点的后指针指向null
        node.next=null;
        //链表长度++
        size++;
    }
    //按下标删除一个节点
    public String removed(int i){
        //先判断下标是否合理
        if (i>=size||i<0) {
            throw new IllegalArgumentException("链表下标越界:" + i);
        }
        //判断是否删除的是头节点
        String result;
        if (i==0){
            result=head.data;
            head=head.next;
            size--;
            return  result;
        }
        //删除的不是头节点
        //找到下标为i-1的节点
        int step=0;
        Node node=head;
        while (step!=i-1){
            step++;
            node=node.next;
        }
        //tmp是下标为被删除节点的位置
        Node tmp=node.next;
        result=tmp.data;
        tmp.pre=node;
        node.next=tmp.next;
        size--;
        return result;
    }
    //按下标插入一个新节点
    public void insert(int i,String data){
        //判断i是否在合理范围内
        if (i>size||i<0){
            throw new IllegalArgumentException("链表下标越界:"+i);
        }
        Node node=new Node(data);
        Node n=head;
        //如果i==0,则说明操作的是头节点
        if (i==0){
            head=node;
            head.next=n;
            n.pre=head;
            size++;
            return;
        }
        int step=0;
        //找到下标为i-1的节点
        while (step!=i-1) {
            n = n.next;
            step++;
        }
        Node n1=n.next;
        n.next=node;
        node.pre=n;
        node.next=n1;
        n1.pre=node.next;
        size++;
    }
    public void printf(){
        Node tmp=head;
        while (tmp.next!=null){
            System.out.print(tmp.data+" ");
            tmp=tmp.next;
        }
        System.out.println();
    }

    public void removeSame(){
        //head=2
        Node n=head;
        while (n.next!=null){
            Node node;
            node=n.next;
            if (Objects.equals(n.data, node.data)){
                n.next=node.next;
            }
            n=n.next;
        }
        printf();
    }

    public static void main(String[] args) {
        Node node=new Node();
        node.add("a");
    }
}
